package Text4;

import java.util.*;

public class Main {
    static int N = 1010;
    static String[] s = new String[N];
    static int[][] f = new int[11][11];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for (int i = 0; i < n; i++) {
            s[i] = in.next();
        }
        while (m-- > 0) {
            String str = in.next();
            int k = in.nextInt();
            int res = 0;
            for (int i = 0; i < n; i++) {
                if (edit_distance(s[i], str) <= k) {
                    res++;
                }
            }
            System.out.println(res);
        }
    }

    private static int edit_distance(String s, String str) {
        int n = s.length();
        int m = str.length();
        for (int i = 0; i <= m; i++) {
            f[0][i] = i;
        }
        for (int i = 0; i <= n; i++) {
            f[i][0] = i;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (s.charAt(i - 1) == str.charAt(j - 1)) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                } else {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        return f[n][m];
    }
}